package interview.heap;

public class Heap {	
	public void sort(int[] array, boolean ascending) {
		if(array == null || array.length == 0)
			return;
		
		int length = array.length;
		buildHeap(array, ascending);
		
		for(int i = length - 1; i > 0; i--) {
			int buf = array[i];
			array[i] = array[0];
			array[0] = buf;
			length--;
			heapify(array, 0, ascending, length);
		}
	}
	
	public void buildHeap(int[] array, boolean ascending) {
		int mid = array.length / 2;
		int length = array.length;
		for(int i = mid; i >= 0; i--) {
			heapify(array, i, ascending, length);
		}
		for(int i : array) {
			System.out.println(i);
		}
	}

	private void heapify(int[] array, int index, boolean ascending, int length) {
		if(ascending) {
			maxheapify(array, index, length);
		} else {
			minheapify(array, index, length);
		}
	}

	private void maxheapify(int[] array, int index, int length) {
		int largest = index;
		int left = index * 2 + 1;
		int right = index * 2 + 2;
		
		if(left < length && array[index] < array[left])
			largest = left;
		
		if(right < length && array[index] < array[right]) {
			largest = right;
		} 
		
		if (largest != index) {
			int buf = array[index];
			array[index] = array[largest];
			array[largest] = buf;
			maxheapify(array, largest, length);
		}
	}

	private void minheapify(int[] array, int index, int length) {
		int smallest = index;
		int left = index * 2 + 1;
		int right = index * 2 + 2;
		
		if(left < length && array[index] > array[left])
			smallest = left;
		
		if(right < length && array[index] > array[right]) {
			smallest = right;
		} 
		
		if (smallest != index) {
			int buf = array[index];
			array[index] = array[smallest];
			array[smallest] = buf;
			minheapify(array, smallest, length);
		}
	}
	
	public int min(int[] array) {
		minheapify(array, 0, array.length);
		return array[0];
	}
	
	public int max(int[] array) {
		maxheapify(array, 0, array.length);
		return array[0];
	}
}
